解題程式碼

var isValidSudoku = function (board) {
  const posSet = new Set();

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === '.') continue;

      const val = board[i][j];
      const boxIndex = `${Math.floor(i / 3)}-${Math.floor(j / 3)}`;
      if (posSet.has(`${val}-${boxIndex}`) || posSet.has(`${val}-col-${j}`) || posSet.has(`${val}-row-${i}`)) return false;

      posSet.add(`${val}-${boxIndex}`).add(`${val}-col-${j}`).add(`${val}-row-${i}`);
    }
  }

  return true;
};

解題思路、演算法

首先用兩層迴圈遍歷，外層迴圈負責遍歷橫列，內層迴圈負責遍歷直欄。

然後用一個 hashMap 將當前遍歷的數字分別記錄到橫列第 i 行，直欄第 j 行，還有九宮格要需要記錄，比較特別的是在哪一個九宮格出現要把行列的值除以 3，所以可能出現的九宮格只會有 00、01、02、10、11、12、20、21、22 共九種。

若檢查記錄前該位置已有數字，就代表有重複的情況，代表此 input 陣列違反數獨規則。

解法的時間、空間複雜度

時間複雜度: O(9^2)
空間複雜度: O(9^2)